Turnbull China Bikeride/Turnbull China Bikeride - Disc 2.iso/BARNET/COMPILER/SATHER/!Sather/Library/Containrs/sa/set_views

Text File | 1996-04-09 | 3KB | 85 lines

---------------------------> Sather 1.1 source file <--------------------------
-- Author: Benedict A. Gomes <[e-mail]>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: set_views.sa,v 1.5 1996/04/09 10:05:28 borisv Exp $
--
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY and is
-- subject to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE
-- contained in the file: Sather/Doc/License of the Sather
-- distribution. The license is also available from ICSI, 1947 Center
-- St., Suite 600, Berkeley CA 94704, USA.
-- -------------------------------------------------------------------
--
--  Views of Sets
--  -------------
-- Several of the set operations return a "view" of the result
-- instead of actually computing it.
-- A view behaves just like any read-only set. However, it operates
-- by having pointers into the original sets, and hence will change
-- whenever the original sets change.
-- This creates a new set a_union_b, which has the actual elements of
-- a and b.
-- Views are defined by the classes BINOP_SET_VIEW and FILTER_SET_VIEW
--
-- The conventional set operations such as union and intersection
-- are provided for convenience, but can be easily and more flexibly
-- achieved (with control over exactly what type of set is created)
-- using set views:
--   a_union_b ::=  #SET{E}(a.union_view(b);
--
-- Design notes on views:
--       class MY_SET_VIEW{T} < $SET{T} is
--            -- A particular implementation must define the following
--            -- routines. See SET_INCL
--            include SET_INCL{T};
--            private create_from_internal(s: $ELT{T}): $SET{T} is
--                  ... ability to create a new set of the same type
--            copy: SAME is ...
--            has(e: E): BOOL is ...
--            size: INT is ...
--            elt!: E is ...
--            insert(e: E);
--            delete(e: E);
--            clear;
--       end;
--  + Low space
--  + Very fast to create - computations are performed at a query
--  + Sometimes the operation need not be even computed
--    (e.g. a.union_view(b).is_empty can return a result as long
--          as there is a single element in either a or b without computing
--          the union at all)
--  + All the set operations may be performed on the result, including
--   getting further views of the result.
--  ? Different semantics
--  - Slightly slower access (extra indirection that might be inlined
--                            away once SAME works properly).
--  - Much slower if set is going to be used repeatedly - instead,
--    convert into a standard set by  #SET{E}(a.union_view(b))

class FILTER_SET_VIEW{ETP} < $RO_SET{ETP} is
   include RO_SET_INCL{ETP};

   private attr pred: ROUT{ETP}:BOOL;
   private attr source: $RO_SET{ETP};

   create(s: $RO_SET{ETP}, predicate: ROUT{ETP}:BOOL): SAME  pre ~void(s) is
      res ::= new;
      res.pred := predicate;
      res.source := s;
      return res;
   end;

   copy: SAME is return create(source,pred) end;
   -- Copy returns a copy of the same type of set

   has(e: ETP): BOOL is
      if source.has(e) then return pred.call(e)  else return false; end;
   end;

   elt!: ETP is
      loop e ::= source.elt!; if pred.call(e) then yield e end; end;
   end;

end;
--=============================================================================